package cg.studio.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

public class QuickSorter implements NumericSorter<Number>
{
  //map of startIndex ==> length;
  private Map< Integer, Integer > envMap = new ConcurrentHashMap< Integer, Integer >();
  private Number[] sortingData = null;
  
  public List<Number> sort( List<Number> orgDatas )
  {
    if( orgDatas == null || orgDatas.size() == 0 || orgDatas.size() == 1 )
      return orgDatas;
    
    envMap.put( 0, orgDatas.size() );
    sortingData = new Number[ orgDatas.size() ];
    int index = 0;
    for( Number data : orgDatas )
    {
      sortingData[index++] = data;
    }
    return sort();
  }
  
  protected List<Number> sort()
  {
    for(;;)
    {
      Set<Integer> startIndexes = envMap.keySet();
      if( startIndexes.isEmpty() )
      {
        List<Number> list = new ArrayList<Number>();
        Collections.addAll( list, sortingData );
        return list;
      }
      for( Integer startIndex : startIndexes )
      {
        sort( startIndex, envMap.remove( startIndex ) );
      }
    }
  }
  
  protected void sort( final int startIndex, int length )
  {
    if( length == 1 )
      return;
    
    int comparingIndex = startIndex;
    int endIndex = startIndex + length - 1;

    //find the number which large than comparing number from left, and number which smaller from right and switch.
    int left = comparingIndex + 1;
    int right = endIndex;
    for(;;)
    {
      for( ; right > left; ++left )
      {
        if( sortingData[ left ].longValue() > sortingData[ comparingIndex ].longValue() )
          break;
      }
      for( ; right > left; --right )
      {
        if( sortingData[ comparingIndex ].longValue() > sortingData[ right ].longValue() )
          break;
      }
      if( left != right )
      {
        //switch
        switchValue( left, right );
      }
      else //left==right
      {
        //left meets right,
        //if this number larger than or equals to comparing, switch comparing with the number before this number;
        //else if this number smaller than comparing, switch comparing with this number
        int splitIndex = left;
        if( sortingData[ left ].longValue() >= sortingData[ comparingIndex ].longValue() )
        {
          if( left-1 > comparingIndex  )
          {
            switchValue( left-1, comparingIndex );
            splitIndex = left-1;
          }
        }
        else if( sortingData[ left ].longValue() < sortingData[ comparingIndex ].longValue() )
        {
          switchValue( left, comparingIndex );
        }
        
        //separate previous array into two arrays[ startIndex, splitIndex-1 ] and [ splitIndex + 1, endIndex ]
        if( splitIndex-startIndex > 1 )
          envMap.put( startIndex, splitIndex-startIndex );
        if( endIndex - splitIndex > 1 )
          envMap.put( splitIndex+1, endIndex - splitIndex  );
        break;
      }
    }

  }
  
  protected void switchValue( int index1, int index2 )
  {
    Number tmpValue = sortingData[ index1 ];
    sortingData[ index1 ] = sortingData[ index2 ];
    sortingData[ index2 ] = tmpValue;
    
  }
  
}
